package com.str.HT;

import com.str.map.Map;

public class DoublyHashedOBHT implements Map {

// Inner class
  private static class Entry {

    // Each ArrayMap.Entry object is a map entry consisting of a key,
    // which is a Comparable object, and a value, which is an arbitrary
    // object.
    Object key;
    Object value;

    Entry(Object k, Object v) {
      key = k;
      value = v;
    }
    	
    public String toString()
    { return "<" + key + "," + value + ">";	}
  }

  private static final Entry FORMER = new Entry(null, null);
  // This guarantees that, for any genuine entry e, 
  // e.key.equals(FORMER.key) returns false.
  private static final int DEFAULT_SIZE = 23;
  private static final double MAX_LOAD_FACTOR = 0.75;
    
  // An object of class OBHT is an open-bucket hash table, containing entries 
  // of class KeyValue.
  private Entry[] array;  
  // array[b] is null if bucket b has never been occupied. 
  // array[b] is FORMER if bucket b is FORMERly-occupied 
  // by an entry that has since been deleted (and not yet replaced).
  private int count;  

// Constructors
  public DoublyHashedOBHT()
  { this(DEFAULT_SIZE); }
   
  public DoublyHashedOBHT(int m) {
    array = new Entry[m];
    count = 0;
  }

// Modifiers
  public void clear() {
  	for (int i = 0; i < array.length; i++)
  	  array[i] = null;
  	count = 0;
  }

  public void add(Object key, Object val) {
    int home = hash(key);
    int pos = home;
    while (array[pos] != null && array[pos] != FORMER) {    
      if (key.equals(array[pos].key)) {
        array[pos].value = val;
        return; 
   	  }     
      pos = (pos + step(key)) % array.length;
      if (pos == home) return;
    }
    if (array[pos] == FORMER) {
      int p = pos;
      do {
        if (key.equals(array[p].key)) {
          array[p] = FORMER;
          count--;
          break; 
   	    }
        p = (p + step(key)) % array.length;
        if (p == home) break;  	    
      } while (array[p] != null); 
    }  
    array[pos] = new Entry(key, val);	
  	if (++count > array.length * MAX_LOAD_FACTOR)
  	  expand();    
  }
  
  public Object remove(Object key) {
  // Delete the entry (if any) whose key is equal to key from this OBHT.
    int home = hash(key);
    int pos = home;
    while (array[pos] != null) {
      if (key.equals(array[pos].key)) {
      	Object temp = array[pos];
        array[pos] = FORMER;
        count--;
        return temp;
      }      
      pos = (pos + step(key)) % array.length;
      if (pos == home) break; 
    }
    return null;
  }

// Accessors  
  public boolean isEmpty() 
  { return count == 0; }

  public int size() 
  { return count; }
  
  public Object getValue(Object key) {
  // Find which if any bucket of this OBHT is occupied by an entry whose key
  // is equal to targetKey. Return the index of that bucket.
    int home = hash(key);
    int pos = home;
    while (array[pos] != null) {
      if (key.equals(array[pos].key)) 
        return array[pos].value;
      pos = (pos + step(key)) % array.length;
      if (pos == home) break;
    }
    return null;
  }

// Auxiliary method  
  private int hash(Object key) {
  // Translate key to an index of the array array.
    return Math.abs(key.hashCode()) % array.length;
  }
  
  private int step(Object key) { 
    return Math.abs(((DoublyHashable) key).stepCode()) % array.length;
  }
    
  private void expand() { 	
    Entry[] oldArray = array;
    int oldSize = array.length;
	int newSize = nextPrime(2 * oldSize);
	array = new Entry[newSize];
    count = 0;
  	for (int i = 0; i < oldSize; i++) {
  	  Entry e = oldArray[i]; 
  	  if (e != null && e != FORMER)
  	    add(e.key, e.value);
  	}
  }
 
  private boolean isPrime(int n) {
    if (n <= 1)
      return false; 	
    if (n == 2 || n == 3)
      return true;
    if (n % 2 == 0)
      return false;
    for (int i = 3; i * i <= n; i += 2)
      if (n % i == 0) return false;
    return true;
  }
  
  private int nextPrime(int n) {
  	if (n < 3) return 3; 
    if (n % 2 == 0) n++;
    while (!isPrime(n)) n += 2;
    return n;
  }
  
  public String toString() {
  	String buf = "";
    for (int i = 0; i < array.length; i++) {
      buf += i + ": ";    
      if (array[i] == FORMER)
        buf += "FORMER";
      else if (array[i] != null)
        buf += array[i];
      buf += "\n";        
    }
    return buf;
  }
}
